package com.Algorithm.HUAWEI.three20220323;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/03/23/15:05
 * @Description:
 * @Target:
 */
public class 迷宫问题 {


    /*
    * 描述
        定义一个二维数组 N*M ，如 5 × 5 数组下所示：

        int maze[5][5] = {
        0, 1, 0, 0, 0,
        0, 1, 1, 1, 0,
        0, 0, 0, 0, 0,
        0, 1, 1, 1, 0,
        0, 0, 0, 1, 0,
        };


        它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。
        入口点为[0,0],既第一格是可以走的路。


        数据范围： 2≤n,m≤10  ， 输入的内容只包含 0≤val≤1

        输入描述：
        输入两个整数，分别表示二维数组的行数，列数。
        再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

        输出描述：
        左上角到右下角的最短路径，格式如样例所示。

        示例1
        输入：
        5 5
        0 1 0 0 0
        0 1 1 1 0
        0 0 0 0 0
        0 1 1 1 0
        0 0 0 1 0
        复制
        输出：
        (0,0)
        (1,0)
        (2,0)
        (2,1)
        (2,2)
        (2,3)
        (2,4)
        (3,4)
        (4,4)
        复制
        示例2
        输入：
        5 5
        0 1 0 0 0
        0 1 0 1 0
        0 0 0 0 1
        0 1 1 1 0
        0 0 0 0 0
        复制
        输出：
        (0,0)
        (1,0)
        (2,0)
        (3,0)
        (4,0)
        (4,1)
        (4,2)
        (4,3)
        (4,4)

        复制
        说明：
        注意：不能斜着走！！
    *
    *
    *
    * */

    // 唯一能肯定的是数上下左右都可以走
    // 先做出走几步能走出去，
    // 条件：左边小于0，右边大于M，上边<0,下边大于N
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] s1 = in.nextLine().split(" ");
        int N = Integer.valueOf(s1[0]);
        int M = Integer.valueOf(s1[1]);
        int[][] ints = new int[N][M];
        int[] ints1 = new int[M*N];
        for (int i = 0; i < N; i++) {
            String[] s = in.nextLine().split(" ");
            for (int j = 0; j < M; j++) {
                ints[i][j] = Integer.valueOf(s[j]);
            }
        }

/*
        int index = 0;
        if (ints[index+1][0]!=0){
            System.out.println(index);
        }


        System.out.println(ints[0][1]);
        System.out.println(ints[1][1]);
        System.out.println(ints[1][2]);
*/
        System.out.println(ints.length);
        System.out.println(ints[0].length);



        Bfs(ints,0,0,ints1);
/*        ArrayList<Integer> list = new ArrayList();


        runWay(ints,0,0,list);

        System.out.println();
        System.out.println();
        System.out.println();
        for (Integer integer : list) {
            System.out.print(integer+" ");
        }*/
    }



    static void Bfs(int[][] ints,int down,int right,int[] count){


        Queue<Integer> queue = new LinkedList();
        queue.add(down*10+right);
        count[down*(ints.length-1)+right] = 1;


        while (!queue.isEmpty()){
            Integer node = queue.poll();


            down = node/10;
            right = node%10;
            System.out.println(down+" "+right);
            while (down<ints.length&&right<ints[0].length){


                if (right+1<ints[0].length && ints[down][right+1]==0 && count[(down)*(ints.length-1)+(right+1)] != 1){
                    count[(down)*(ints.length-1)+(right+1)] = 1;
                    queue.add(down*10+(right+1));
                }
                if (right>0 && ints[down][right-1]==0 && count[(down)*(ints.length-1)+(right-1)] != 1){
                    count[(down)*(ints.length-1)+(right-1)] = 1;
                    queue.add(down*10+(right-1));
                }

                if (down+1<ints.length && ints[down+1][right]==0  && count[(down+1)*(ints.length-1)+(right)] != 1){
                    count[(down+1)*(ints.length-1)+(right)] = 1;
                    queue.add((down+1)*10+(right));
                }

                if (down>0 && ints[down-1][right]==0 && count[(down-1)*(ints.length-1)+(right)] != 1){
                    count[(down-1)*(ints.length-1)+(right)] = 1;
                    queue.add((down-1)*10+(right));
                }


                down++;
                right++;
            }

        }



    }





    static void runWay(int[][] ints, int down, int right, ArrayList<Integer> memoryList){
        if (memoryList.contains(down*10+right)){
//            removeTargetBehind(memoryList,(down*10+right));
            return;
        }

        memoryList.add(down*10+right);
        System.out.println(down+" "+right);
        if (right==ints[0].length-1&&down==ints.length-1){
            System.out.println("OK");
        }


        if (right+1<ints[0].length&&ints[down][right+1]==0){
            runWay(ints,down,right+1,memoryList);
        }
        if (right>0&&ints[down][right-1]==0){
            runWay(ints,down,right-1,memoryList);
        }

        if (down+1<ints.length&&ints[down+1][right]==0){
            runWay(ints,down+1,right,memoryList);
        }

        if (down>0&&ints[down-1][right]==0){
            runWay(ints,down-1,right,memoryList);
        }


    }


    static ArrayList<Integer> removeTargetBehind(ArrayList<Integer> list,int num){
        ArrayList list1 = new ArrayList();
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i)!=num){
                list1.add(list.get(i));
            }else {
                list = null;
                break;
            }

        }

        return list1;
    }


}
